package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DivideConquer;
import cn.pugle.oj.catalog.Unknown;

/**
 * 啊啊啊啊 二分查找我疯了
 * AC了, 但是好像慢啊, TODO
 * //另一种思路是, 我上面比较的时候拿出了两个值和target比较进行分割, 也可以拿出四个值比较进行分割.
 * //另一种思路是, 第一行二分搜, 然后拿着结果第二行二分搜....
 *
 * @author tzp
 * @since 2020/10/19
 */
public class LC240_1 implements DivideConquer {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        return search(matrix, target, 0, matrix.length - 1, 0, matrix[0].length - 1);
    }

    /**
     * 本题查找的是左确界
     */
    public boolean search(int[][] matrix, int target, int rs, int re, int cs, int ce) {
        if (rs > re || cs > ce
                || rs < 0 || re >= matrix.length
                || cs < 0 || ce >= matrix[0].length) return false;
        if (re - rs <= 1 && ce - cs <= 1) {
            for (int i = rs; i <= re; i++) {
                for (int j = cs; j <= ce; j++) {
                    if (matrix[i][j] == target) return true;
                }
            }
            return false;
        }
        int midR = rs + ((re - rs) >> 1);
        int midC = cs + ((ce - cs) >> 1);

        //两个mid都比target大, 找左上
        //两个mid都比target小, 找除了左上的3个.
        //rowMid比t小, colMid比t大, 找左上, 左下
        if (matrix[midR][cs] == target || matrix[rs][midC] == target) {
            return true;
        } else if (matrix[midR][cs] > target && matrix[rs][midC] > target) {
            return search(matrix, target, rs, midR, cs, midC);//左上
        } else if (matrix[midR][cs] < target && matrix[rs][midC] < target) {
            return search(matrix, target, midR, re, cs, midC) ||//左下
                    search(matrix, target, rs, midR, midC, ce) ||//右上
                    search(matrix, target, midR, re, midC, ce);//右下
        } else if (matrix[midR][cs] < target && matrix[rs][midC] > target) {
            return search(matrix, target, midR, re, cs, midC) ||//左下
                    search(matrix, target, rs, midR, cs, midC);//左上
        } else if (matrix[midR][cs] > target && matrix[rs][midC] < target) {
            return search(matrix, target, rs, midR, midC, ce) ||//右上
                    search(matrix, target, rs, midR, cs, midC);//左上
        } else {
            return false;//never
        }
    }


    public static void main(String[] args) {
        int[][] m = {
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
        System.out.println(new LC240_1().searchMatrix(m, 4));
        for (int i = 1; i <= 30; i++) {
            System.out.println(i + " " + new LC240_1().searchMatrix(m, i));
        }
    }
}
